package com.zp.self.module.level_4_算法练习.算法.排序;

import com.google.common.collect.Lists;
import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class VIIII_桶排序_O_nXlogn {
    @Test
    public void main() {
        System.out.println(new VIIII_桶排序_O_nXlogn().bucketSort(Lists.newArrayList(7,1,5,3,6,4,8,2),4));
    }

    /**
    题目：桶排序：应用场景？？

    分析：
     桶排序：时间：O(n+k -- n*n) 、空间：O(k)、顺序稳定
            实现：1.遍历数组：通过值区间大小[max -min+1]、除以宽度bucketSize==桶个数
                  2.遍历数组，将(元素-min) / bucketSize  得到需要放到哪个桶中
                  3.分别排序每个桶，并将桶中元素存储到返回的集合中
     **/
    /**
     * @param array 目标数组
     * @param bucketSize 每个桶的宽度
     */
    public List<Integer> bucketSort(List<Integer> array, int bucketSize) {
        if (array == null || array.size() < 2 || bucketSize < 1) return array;
        //1.找出元素中最大值和最小值
        int max = array.get(0), min = array.get(0);
        for (Integer anArray1 : array) {
            if (anArray1 > max) max = anArray1;
            if (anArray1 < min) min = anArray1;
        }
        //计算桶个数 min~max表示桶数据的取值范围。 +1是为什么？ 答：因为余数要放一个桶，eg:范围是5 ,bucketSize =4 .这时不就需要两个桶吗
        int bucketCount = (max - min+1) / bucketSize +(((max - min+1) % bucketSize) ==0 ? 0:1) ;
        //2.按照顺序创建桶 list嵌套list
        List<List<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) bucketList.add(new LinkedList<>());
        //把待排序的集合依次添加待对应的桶中
        for (Integer anArray : array) {
            bucketList.get((anArray - min) / bucketSize).add(anArray); //得到对应数据的桶的索引
        }
        //3.对桶中数据排序 使用sort()方法实现
        List<Integer> result = new ArrayList<>();
        for (List<Integer> list : bucketList) {
            list.sort((a, b) -> (a - b));//升序
            result.addAll(list);
        }
        return result;
    }

}
